package xin.javashare.sort;

/**
 * 程序清单7.8 【选择排序】P229
 * 时间复杂度O(n^2)
 * 升序排列一个数列。先找到数列中最小的数和第一个元素交换，
 * 然后在剩下的数中找最小的数和第二个元素交换，
 * 以此类推，直到只剩下一个数为止。
 */
public class SelectionSort2 {
    // 升序排列方法
    public static void selectionSort(int[] list) {
        for (int i = 0; i < list.length - 1; i++) {
            int currentMin = list[i];
            int currentMinIndex = i;
            for (int j = i + 1; j < list.length; j++) {
                if (currentMin > list[j]) {
                    currentMin = list[j];
                    currentMinIndex = j;
                }
            }

            if (currentMinIndex != i) {
                list[currentMinIndex] = list[i];
                list[i] = currentMin;
            }
        }
    }

    // 降序排列方法
    public static void selectionSort2(int[] list) {
        for (int i = 0; i < list.length - 1; i++) {
            int currentMax = list[i];
            int currentMaxIndex = i;
            for (int j = i + 1; j < list.length; j++) {
                if (currentMax < list[j]) {
                    currentMax = list[j];
                    currentMaxIndex = j;
                }
            }

            if (currentMaxIndex != i) {
                list[currentMaxIndex] = list[i];
                list[i] = currentMax;
            }

        }
    }

    public static void selectionSort3(int[] list) {
        int size = list.length;
        int temp = 0;
        for (int i = 0; i < size - 1; i++) {
            for (int j = i + 1; j < size; j++) {
                if (list[j] < list[i]) {
                    temp = list[i];
                    list[i] = list[j];
                    list[j] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] list = {-2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
        selectionSort3(list);
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + " ");
        }
        System.out.println("\n----------------------");
        selectionSort2(list);
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + " ");
        }
        System.out.println("\n--调用quickSort()方法---");
        QuickSort.quickSort(list);
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + " ");
        }
    }
}
